package leetcode_jz_offer.day2_list;

/**
 * 请实现 copyRandomList 函数，复制一个复杂链表。
 * 在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null
 * 链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
 * lettcode138  or leetcode - jianzhi35
 **/
/**
 * 分析：
 * 1.先不管random，就进行普通链表的深拷贝：边遍历原链表，每当走到一个原链表的节点就创建一个新节点，值与原链表相同
 * 链表链接：next的连接：创建一个虚拟头节点，进行尾插法，就可以连接新链表的next域
 * 2.random的连接：很难进行操作：换思路
 * //注意：在做数据结构和算法题是，不要看是链表题就只想着链表，注意换思路
 * //Map接口=》映射：Map<K,V>:一个k对应一个v,新链表和原链表除了地址不同，其余对应关系完全相同，原1=>新1；原2=>新2
 * 新链表的next和random都可以从原链表中一一映射过来
 * 思路：
 * Map集合键值对对应旧链表的节点与新链表的节点（一个旧链表节点肯定对应一个新链表节点）
 * 边遍历原链表边构造新链表,将它们对应的结点放在Map集合中,构成一个映射关系，通过映射关系连线
 */
import java.util.HashMap;
import java.util.Map;

/**
 * 通过Map的映射关系进行映射
 * 将原结点放到key中,同时对应建一个新节点,新节点值和原结点相同,放到val中.此时原结点一定对应新节点
 */
public class Num35_CopyList {
    private class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();
        //遍历原链表，对应创建新链表，两者的结点存入map中
        for(Node x=head;x!=null;x=x.next){
            Node newNode=new Node(x.val);
            map.put(x,newNode);
        }
        //新链表和原链表就是映射关系，进行连线
        //next和random都是与原链表对应的
        for(Node x=head;x!=null;x=x.next){
            map.get(x).next= map.get(x.next);//新结点的next指向下一个新节点
            map.get(x).random=map.get(x.random);//老节点x的random是x.random，两者对应的映射自然是新节点的连线规则
        }
        return map.get(head);//返回新链表的头节点，就是原链表头节点的映射
    }

}
